package woman;

public class Tree
{
	public class Element
	{
		int num;
		Element left_child;
		Element right_child;
		Element iam;
		Element parent;
		
		public Element(int num, Element parent)
		{
			this.num = num;
			this.left_child = null;
			this.right_child = null;
			this.iam = this;
			this.parent = parent;
		}
	}
	
	Element root;
	int lenght;
	
	public Tree()
	{
		root = null;
		lenght = 0;		
	}
	
	public Tree(int num)
	{
		root = new Element(num, null);
		lenght = 1;
	}

	public Element insert(int num)
	{
		lenght++;
		if(root == null)
		{
			root = new Element(num, null);
			return root; 
		}
		
		Element Element = root;
		while(Element != null)
			if(num >= Element.num)
				if(Element.right_child == null)
				{
					Element.right_child = new Element(num, Element);
					return Element.right_child;
				}
				else
					Element = Element.right_child;
			else if(num < Element.num)
				if(Element.left_child == null)
				{
					Element.left_child = new Element(num, Element);
					return Element.left_child;
				}
				else
					Element = Element.left_child;
		
		lenght--;
		return null;
	}
	
	public void printTree()
	{
		System.out.println("\nLenght: " + lenght);
		printTree(root, 0);
	}
	
	private void printTree(Element Element, int level)
	{
		 if(Element.right_child != null)
			 printTree(Element.right_child, level+1);
		 
		 for(int i = 0; i < level; i++)
			 System.out.print("\t");
		 System.out.println(Element.num);
		 
		 if(Element.left_child != null)
			 printTree(Element.left_child, level+1);
	}
	
	public Element search(int num)
	{
		Element minElement = root;
		Element maxElement = root;
		
		Element Element = root;
		while(Element != null)
			if(num == Element.num)
				return Element;
			else if(num > Element.num)
			{
				if(maxElement.num < Element.num)
					maxElement = Element;
				minElement = Element;
				Element = Element.right_child;
			}
			else if(num < Element.num)
			{
				if(minElement.num > Element.num)
					minElement = Element;
				maxElement = Element;
				Element = Element.left_child;
			}
		
		if(maxElement.num - num <= num - minElement.num)
			return maxElement;
		else
			return minElement;
	}

	public Element Maximum()
	{
		Element Element = root;
		while(Element.right_child != null)
			Element = Element.right_child;
		return Element;
	}
		
	public Element Minimum()
	{
		Element Element = root;
		while(Element.left_child != null)
			Element = Element.left_child;
		return Element;
	}

	public boolean Delete(int num)
	{
		return Delete(num, root);
	}
	
	private boolean Delete(int num, Element Element)
	{
		while(Element != null)
		{
			if(num < Element.num)
				Element = Element.left_child;
			else if(num > Element.num)
				Element = Element.right_child;
			else if(num == Element.num)
			{
				if(Element.left_child != null && Element.right_child != null)
				{
					if(Element.right_child.left_child == null)
					{
						Element.right_child.left_child = Element.left_child;
						
						if(Element == root)
							root = Element.right_child;
						else if(Element.parent.left_child == Element)
							Element.parent.left_child = Element.right_child;
						else if(Element.parent.right_child == Element)
							Element.parent.right_child = Element.right_child;
						lenght--;
						return true;
					}
					else
					{
						Element Elementleft_child = Element.right_child.left_child;
						while(Elementleft_child.left_child != null)
							Elementleft_child = Elementleft_child.left_child;
						Element.num = Elementleft_child.num;
						return Delete(Elementleft_child.num, Elementleft_child);
					}
				}
				else	
				{
					if(Element.left_child == null && Element.right_child == null)
					{
						if(Element == root)
							root = null;
						else if(Element.parent.left_child == Element)
							Element.parent.left_child = null;
						else if(Element.parent.right_child == Element)
							Element.parent.right_child = null;
					}
					else if(Element.left_child != null)
					{
						if(Element == root)
							root = Element.left_child;
						else if(Element.parent.left_child == Element)
							Element.parent.left_child = Element.left_child;
						else if(Element.parent.right_child == Element)
							Element.parent.right_child = Element.left_child;
					}
					else if(Element.right_child != null)
					{
						if(Element == root)
							root = Element.right_child;
						else if(Element.parent.left_child == Element)
							Element.parent.left_child = Element.right_child;
						else if(Element.parent.right_child == Element)
							Element.parent.right_child = Element.right_child;
					}
					lenght--;
					return true;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args)
	{
		Tree tree = new Tree();
		
		int n = 5;
		System.out.println("Binaty_Tree");
		for(int i = 0; i < n; i++)
		{
			int number = (int) (Math.random()*n*2-n);
			System.out.print(number + ",");
			tree.insert(number);
		}
		
		tree.printTree();

		int search = (int) (Math.random()*n*2-n);
		int Num = tree.search(search).num;
		System.out.println("Search: " + search);
		System.out.println("Search Num: " + Num);
		System.out.println("Delete: " + Num + " : " + tree.Delete(Num));
		System.out.println("Delete: " + Num/2 + " : " + tree.Delete(Num/2));
		System.out.println("Address minimum: " + tree.Minimum());
		System.out.println("Address maximum: " + tree.Maximum());
		
		tree.printTree();
	}
}
